package leetcode.offer_two_special.tree;

import leetcode.tree.common.TreeNode;

import java.util.*;

/**
 * @author mazouri
 * @create 2021-09-12 23:28
 */
public class _56_findTarget {
    /**
     * 迭代
     *
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget1(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (set.contains(k - cur.val)) return true;

            set.add(cur.val);
            cur = cur.right;
        }
        return false;
    }


    /**
     * 递归+双指针
     *
     * @param root
     * @param k
     * @return
     */
    ArrayList<Integer> list = new ArrayList<>();

    public boolean findTarget2(TreeNode root, int k) {
        dfs(root);
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            int sum = list.get(left) + list.get(right);
            if (sum == k) return true;
            else if (sum > k) right--;
            else left++;
        }
        return false;
    }

    private void dfs(TreeNode root) {
        if (root != null) {
            dfs(root.left);
            list.add(root.val);
            dfs(root.right);
        }
    }


    HashSet<Integer> set = new HashSet<>();
    int k;

    public boolean findTarget(TreeNode root, int k) {
        this.k = k;
        return find(root);
    }

    public boolean find(TreeNode root) {
        if (root == null) return false;

        if (set.contains(k - root.val)) return true;
        set.add(root.val);

        return find(root.left) || find(root.right);
    }
}
